

<!DOCTYPE html>
<html lang="zh-CN" data-default-color-scheme=&#34;auto&#34;>



<head>
  <meta charset="UTF-8">
  <link rel="apple-touch-icon" sizes="76x76" href="/blog/img/favicon.png">
  <link rel="icon" type="image/png" href="/blog/img/favicon.png">
  <meta name="viewport"
        content="width=device-width, initial-scale=1.0, maximum-scale=1.0, user-scalable=no, shrink-to-fit=no">
  <meta http-equiv="x-ua-compatible" content="ie=edge">
  
    <meta http-equiv="Content-Security-Policy" content="upgrade-insecure-requests">
  
  <meta name="theme-color" content="#fff">
  <meta name="description" content="その時を待つよ">
  <meta name="author" content="Isshiki_Hugh">
  <meta name="keywords" content="">
  <title>algorithm-历届程序填空专题 - Isshiki&#39;sBlog</title>

  <link  rel="stylesheet" href="https://cdn.staticfile.org/twitter-bootstrap/4.4.1/css/bootstrap.min.css" />


  <link  rel="stylesheet" href="https://cdn.staticfile.org/github-markdown-css/4.0.0/github-markdown.min.css" />
  <link  rel="stylesheet" href="/blog/lib/hint/hint.min.css" />

  
    
    <link  rel="stylesheet" href="https://cdn.staticfile.org/highlight.js/10.0.0/styles/atom-one-dark.min.css" />
  

  


<!-- 主题依赖的图标库，不要自行修改 -->

<link rel="stylesheet" href="//at.alicdn.com/t/font_1749284_6peoq002giu.css">



<link rel="stylesheet" href="//at.alicdn.com/t/font_1736178_pjno9b9zyxs.css">


<link  rel="stylesheet" href="/blog/css/main.css" />

<!-- 自定义样式保持在最底部 -->


  <script  src="/blog/js/utils.js" ></script>
  <script  src="/blog/js/color-schema.js" ></script>
<meta name="generator" content="Hexo 5.0.2"></head>


<body>
  <header style="height: 75vh;">
    <nav id="navbar" class="navbar fixed-top  navbar-expand-lg navbar-dark scrolling-navbar">
  <div class="container">
    <a class="navbar-brand"
       href="/blog/">&nbsp;<strong>Isshiki修のBlog</strong>&nbsp;</a>

    <button id="navbar-toggler-btn" class="navbar-toggler" type="button" data-toggle="collapse"
            data-target="#navbarSupportedContent"
            aria-controls="navbarSupportedContent" aria-expanded="false" aria-label="Toggle navigation">
      <div class="animated-icon"><span></span><span></span><span></span></div>
    </button>

    <!-- Collapsible content -->
    <div class="collapse navbar-collapse" id="navbarSupportedContent">
      <ul class="navbar-nav ml-auto text-center">
        
          
          
          
          
            <li class="nav-item">
              <a class="nav-link" href="/blog/">
                <i class="iconfont icon-home-fill"></i>
                首页
              </a>
            </li>
          
        
          
          
          
          
            <li class="nav-item">
              <a class="nav-link" href="/blog/archives/">
                <i class="iconfont icon-archive-fill"></i>
                归档
              </a>
            </li>
          
        
          
          
          
          
            <li class="nav-item">
              <a class="nav-link" href="/blog/categories/">
                <i class="iconfont icon-category-fill"></i>
                分类
              </a>
            </li>
          
        
          
          
          
          
            <li class="nav-item">
              <a class="nav-link" href="/blog/tags/">
                <i class="iconfont icon-tags-fill"></i>
                标签
              </a>
            </li>
          
        
          
          
          
          
            <li class="nav-item">
              <a class="nav-link" href="/blog/about/">
                <i class="iconfont icon-user-fill"></i>
                关于
              </a>
            </li>
          
        
          
          
          
          
            <li class="nav-item">
              <a class="nav-link" href="/blog/links/">
                <i class="iconfont icon-link-fill"></i>
                友链
              </a>
            </li>
          
        
        
          <li class="nav-item" id="search-btn">
            <a class="nav-link" data-toggle="modal" data-target="#modalSearch">&nbsp;<i
                class="iconfont icon-search"></i>&nbsp;</a>
          </li>
        
        
          <li class="nav-item" id="color-toggle-btn">
            <a class="nav-link" href="javascript:">&nbsp;<i
                class="iconfont icon-dark" id="color-toggle-icon"></i>&nbsp;</a>
          </li>
        
      </ul>
    </div>
  </div>
</nav>

    <div class="banner intro-2" id="background" parallax=true
         style="background: url('/blog/img/default.JPG') no-repeat center center;
           background-size: cover;">
      <div class="full-bg-img">
        <div class="mask flex-center" style="background-color: rgba(0, 0, 0, 0.3)">
          <div class="container page-header text-center fade-in-up">
            <span class="h2" id="subtitle">
              
            </span>

            
              
  <div class="mt-3 post-meta">
    <i class="iconfont icon-date-fill" aria-hidden="true"></i>
    <time datetime="2019-10-17 08:17" pubdate>
      2019年10月17日 早上
    </time>
  </div>


<div class="mt-1">
  
    
    <span class="post-meta mr-2">
      <i class="iconfont icon-chart"></i>
      372 字
    </span>
  

  
    
    <span class="post-meta mr-2">
      <i class="iconfont icon-clock-fill"></i>
      
      
      5
       分钟
    </span>
  

  
  
    
      <!-- 不蒜子统计文章PV -->
      <span id="busuanzi_container_page_pv" style="display: none">
        <i class="iconfont icon-eye" aria-hidden="true"></i>
        <span id="busuanzi_value_page_pv"></span> 次
      </span>
    
  
</div>

            
          </div>

          
        </div>
      </div>
    </div>
  </header>

  <main>
    
      

<div class="container-fluid">
  <div class="row">
    <div class="d-none d-lg-block col-lg-2"></div>
    <div class="col-lg-8 nopadding-md">
      <div class="container nopadding-md" id="board-ctn">
        <div class="py-5" id="board">
          <article class="post-content mx-auto" id="post">
            <!-- SEO header -->
            <h1 style="display: none">algorithm-历届程序填空专题</h1>
            
              <p class="note note-info">
                
                  本文最后更新于：1 年前
                
              </p>
            
            <div class="markdown-body" id="post-body">
              <h3 id="0-x-前言"><a href="#0-x-前言" class="headerlink" title="[0.x]前言"></a>[0.x]前言</h3><p>本文针对<script type="math/tex">CSP-S_{(初赛)}</script></p>
<p>题目来源：NOIP 2007 ~ NOIP 2018（初赛）<em>(缩进有部分调整)</em></p>
<p>语言：$Cpp$</p>
<p><del>我吐了，我似乎挖了一个大坑orz，一题写一年系列orz</del></p>
<p><strong>Tips</strong>:可以通过侧栏目录索引</p>
<a id="more"></a>
<h3 id="目录"><a href="#目录" class="headerlink" title="目录"></a>目录</h3><ul>
<li>[0.x]前言</li>
<li>[1.x]NOIP 2007<ul>
<li>[1.1]T27 格雷码</li>
<li>[1.2]T28 连续邮资问题</li>
</ul>
</li>
<li>[2.x]NOIP 2008<ul>
<li>[2.1]T27 找第k大数</li>
<li>[2.2]T28 矩阵中的数字</li>
</ul>
</li>
<li>[3.x]NOIP 2009<ul>
<li>[3.1] T27 最大连续字段和</li>
<li>[3.2] T28 寻找等差数列</li>
</ul>
</li>
</ul>
<hr>
<h3 id="1-x-NOIP-2007"><a href="#1-x-NOIP-2007" class="headerlink" title="[1.x]NOIP 2007"></a>[1.x]NOIP 2007</h3><h4 id="1-1-T27-格雷码"><a href="#1-1-T27-格雷码" class="headerlink" title="[1.1]T27 格雷码"></a>[1.1]T27 格雷码</h4><p>格雷码是对十进制数的一种二进制编码。编码顺序与相应的十进制数的大小不一致。其特点是：对于两个相邻的十进制数，对应的两个格雷码只有一个二进制位不同。另外，最大数与最小数之间也仅有一个二进制位不同，以4 位二进制数为例，编码如下：</p>
<div class="table-container">
<table>
<thead>
<tr>
<th>十进制数</th>
<th>格雷码</th>
<th>十进制数</th>
<th>格雷码</th>
</tr>
</thead>
<tbody>
<tr>
<td>0</td>
<td>0000</td>
<td>8</td>
<td>1100</td>
</tr>
<tr>
<td>1</td>
<td>0001</td>
<td>9</td>
<td>1101</td>
</tr>
<tr>
<td>2</td>
<td>0011</td>
<td>10</td>
<td>1111</td>
</tr>
<tr>
<td>3</td>
<td>0010</td>
<td>11</td>
<td>1110</td>
</tr>
<tr>
<td>4</td>
<td>0110</td>
<td>12</td>
<td>1010</td>
</tr>
<tr>
<td>6</td>
<td>0111</td>
<td>13</td>
<td>1011</td>
</tr>
<tr>
<td>7</td>
<td>0101</td>
<td>14</td>
<td>1001</td>
</tr>
<tr>
<td>8</td>
<td>0100</td>
<td>15</td>
<td>1000</td>
</tr>
</tbody>
</table>
</div>
<p>如果把每个二进制的位看作一个开关，则将一个数变为相邻的另一个数，只须改动一个开关。因此，格雷码广泛用于信号处理、数-模转换等领域。</p>
<p>下面程序的任务是：由键盘输入二进制数的位数<script type="math/tex">n(n<16)</script>，再输入一个十进制数<script type="math/tex">m(0≤m<2n)</script>，然后输出对应于<script type="math/tex">m</script>的格雷码（共<script type="math/tex">n</script>位，用数组<script type="math/tex">gr</script>[]​存放）。</p>
<p>为了将程序补充完整，你<strong>必须认真分析</strong>（疯狂暗示）上表的规律，特别是对格雷码固定的某一位，从哪个十进制数起，由<script type="math/tex">0</script>变为<script type="math/tex">1</script>，或由<script type="math/tex">1</script>变为<script type="math/tex">0</script>。</p>
<div class="hljs"><pre><code class="hljs cpp"><span class="hljs-meta">#<span class="hljs-meta-keyword">include</span> <span class="hljs-meta-string">&lt;stdio.h&gt;</span></span>
<span class="hljs-function"><span class="hljs-keyword">void</span> <span class="hljs-title">main</span><span class="hljs-params">()</span></span>&#123;
    <span class="hljs-keyword">int</span> bound = <span class="hljs-number">1</span>, m, n, i, j, b, p, gr[<span class="hljs-number">15</span>];
    <span class="hljs-built_in">printf</span>( <span class="hljs-string">&quot;input n,m\n&quot;</span> );
    <span class="hljs-built_in">scanf</span>( <span class="hljs-string">&quot;%d%d&quot;</span>, &amp;n, &amp;m );
    <span class="hljs-keyword">for</span> ( i = <span class="hljs-number">1</span>; i &lt;= n; i++ )
        bound =(___①___);
    <span class="hljs-keyword">if</span> ( m &lt; <span class="hljs-number">0</span> || m &gt;= bound )
    &#123;
        <span class="hljs-built_in">printf</span>( <span class="hljs-string">&quot;Data error!\n&quot;</span> );
        (___②___);
    &#125;
    b = <span class="hljs-number">1</span>;
    <span class="hljs-keyword">for</span> ( i = <span class="hljs-number">1</span>; i &lt;= n; i++ )
    &#123;
        p = <span class="hljs-number">0</span>; b = b * <span class="hljs-number">2</span>;
        <span class="hljs-keyword">for</span> ((___③___); j &lt;= m; j++ )
            <span class="hljs-keyword">if</span> (___④___)
                p = <span class="hljs-number">1</span> - p;
        gr[i] = p;
    &#125;
    <span class="hljs-keyword">for</span> ( i = n;i &gt;= <span class="hljs-number">1</span>;i--)<span class="hljs-comment">//本来这里还有一空的，可是我搜到的题目有点小瑕疵，所以我直接填上了xd</span>
        <span class="hljs-built_in">printf</span>( <span class="hljs-string">&quot;%1d&quot;</span>, gr[i] );  <span class="hljs-comment">/* 在&quot;%1d&quot; 中出现的是数字1，不是字母l */</span>
    <span class="hljs-built_in">printf</span>( <span class="hljs-string">&quot;\n&quot;</span> );</code></pre></div>
<p> 1.<code>_______________</code><br> 2.<code>_______________</code><br> 3.<code>_______________</code><br> 4.<code>_______________</code></p>
<div class='spoiler collapsed'>
    <div class='spoiler-title'>
        解析&答案
    </div>
    <div class='spoiler-content'>
        <p>观察程序可以得到：</p>
<p>$n$表示二进制长度，<script type="math/tex">m</script>表示十进制数。</p>
<p>下一行出现了一个<script type="math/tex">for</script>循环，而循环内仅修改<script type="math/tex">bound</script>，很容易猜测这是个<strong>累乘</strong><script type="math/tex">(bound=bound*k)</script>或者<strong>累加</strong><script type="math/tex">(bound=bound+k)</script>的过程，至于究竟是什么，还需要看它的用处。于是我们开心的发现下一行就用到了。看<script type="math/tex">printf</script>的内容我们就知道这是一个判定输入错误的语句，根据括号内的内容我们很容易得出它是在判定<script type="math/tex">m</script>是否超界，而<script type="math/tex">bound</script>就代表了上界(不包含在可取范围内，从”&lt;=”可以取等看出)。</p>
<p>那么这题的上界由什么决定呢？很显然是由二进制长度决定的，每一个十进制数和每一个二进制码是一一对应的，因此可以表示的十进制数必然是有限的，长度为<script type="math/tex">n</script>的二进制<strong>最多表示<script type="math/tex">2^n</script>个不同的数</strong>，而这里<strong>从<script type="math/tex">0</script>开始</strong>，所以我们可以得到<script type="math/tex">bound=2^n</script>。因此<script type="math/tex">1</script>必然是个累乘的过程，<script type="math/tex">2</script>就是<code>bound*2​</code>。</p>
<p>由于判定语句用来判定输入是否合法，如果不合法只能<strong>停止</strong>程序，所以<script type="math/tex">2</script>为<code>return</code></p>
<p>然后就设计格雷码的核心操作了。也就是这道题的精髓。我们观察核心程序，发现作为格雷码下标的<script type="math/tex">i</script>在一个叫<script type="math/tex">j</script>的外面，而j的变化范围又是<script type="math/tex">1</script>~<script type="math/tex">m</script>。结合题目中的疯狂暗示，当我们<strong>按位</strong>来<strong>竖</strong>着读表，便会发现很神奇的规律。这时候你又发现有个叫<script type="math/tex">b</script>的在偷偷累乘，就可以得出每一位的<script type="math/tex">0</script>和<script type="math/tex">1</script>是以<script type="math/tex">b</script>为单位在<strong>循环</strong>。那么我们就可以来做剩下的空了。</p>
<p>我们现在不把<script type="math/tex">m</script>当做一个数，而是把<script type="math/tex">m</script>当做<script type="math/tex">m</script>在这个表中竖向的位置。也就是<script type="math/tex">m</script>是<strong>这张表从上往下数的第<script type="math/tex">m+1</script>个</strong>，以最低位为例子，我们可以得到变化频率如此：<script type="math/tex">0</script>   <script type="math/tex">1</script>   <script type="math/tex">1</script>   <script type="math/tex">0</script>   <script type="math/tex">0</script>   <script type="math/tex">1</script>   <script type="math/tex">1</script>   <script type="math/tex">...</script> ，此时<script type="math/tex">b = 2</script></p>
<p>结合循环上界为<script type="math/tex">m</script>，为了进行<script type="math/tex">m+1</script>次循环，我们把起点设置为<script type="math/tex">0</script>，即3.<code>j=0</code></p>
<p>对于循环，需要注意先从<script type="math/tex">0</script>开始滚<script type="math/tex">\frac{b}{2}</script><strong>后</strong>开始<script type="math/tex">b</script>为单位的循环，可以理解为一开始已经滚了<script type="math/tex">\frac{b}{2}</script>。所以4.<code>(j+b/2)%b==0</code>或者其等效语句</p>
<p>1.<code>bound*2</code><br>2.<code>return</code><br>3.<code>j=0</code><br>4.<code>(j+b/2)%b==0</code> 或 <code>!(j+b/2)%b</code> 或  <code>j%b+b/2==0</code> 等</p>

    </div>
</div>
<h4 id="1-2-T28-连续邮资问题"><a href="#1-2-T28-连续邮资问题" class="headerlink" title="[1.2]T28 连续邮资问题"></a>[1.2]T28 连续邮资问题</h4><p>某国发行了<script type="math/tex">n</script>种不同面值的邮票，并规定每封信最多允许贴<script type="math/tex">m</script>张邮票，在这些约束下，为了能贴出<script type="math/tex">\{1，2，3,…，maxvalue\}</script>连续整数集合的所有邮资，并使<script type="math/tex">maxvalue</script>的值最大，应该如何设计各邮票的面值？例如，当<script type="math/tex">n=5</script>、<script type="math/tex">m=4</script>时，面值设计为<script type="math/tex">\{1，3，11，15，32\}</script>，可使<script type="math/tex">maxvalue</script>达到最大值<script type="math/tex">70</script>（或者说，用这些面值的<script type="math/tex">1</script>至<script type="math/tex">4</script>张邮票可以表示不超过<script type="math/tex">70</script>的所有邮资，但无法表示邮资<script type="math/tex">71</script>。而用其他面值的<script type="math/tex">1</script>至<script type="math/tex">4</script>张邮票如果可以表示不超过<script type="math/tex">k</script>的所有邮资，必有<script type="math/tex">k≤70</script>）。</p>
<p>下面是用<strong>递归回溯</strong>求解连续邮资问题的程序。数组<script type="math/tex">x[1</script>~<script type="math/tex">n]</script>表示<script type="math/tex">n</script>种不同的邮票面值，并约定各元素按下标是<strong>严格递增</strong>的。数组<script type="math/tex">bestx [1</script>~<script type="math/tex">n]</script>存放使<script type="math/tex">maxvalue</script>达到最大值的邮票面值（最优解），数组<script type="math/tex">y[maxl]</script>用于记录当前已选定的邮票面值<script type="math/tex">x[1</script>~<script type="math/tex">i]</script>能贴出的各种邮资所需的最少邮票张数。请将程序补充完整。</p>
<div class="hljs"><pre><code class="hljs cpp"><span class="hljs-meta">#<span class="hljs-meta-keyword">include</span> <span class="hljs-meta-string">&lt;stdio.h&gt;</span></span>
<span class="hljs-meta">#<span class="hljs-meta-keyword">define</span> NN = 20</span>
<span class="hljs-meta">#<span class="hljs-meta-keyword">define</span> maxint = 30000</span>
<span class="hljs-meta">#<span class="hljs-meta-keyword">define</span> maxl = 500 <span class="hljs-comment">/*邮资的最大值*/</span></span>
<span class="hljs-keyword">int</span> n, m, bestx[NN], x[NN], y[maxl], maxvalue = <span class="hljs-number">0</span>;
<span class="hljs-function"><span class="hljs-keyword">void</span> <span class="hljs-title">result</span><span class="hljs-params">()</span></span>&#123;输出结果 ： 最 大 值 ： maxvalue 及 最 优 解 ： bestx[<span class="hljs-number">1</span> : n] (略&#125;
<span class="hljs-keyword">void</span> backtrace( <span class="hljs-keyword">int</span> i, <span class="hljs-keyword">int</span> r )&#123;<span class="hljs-comment">//需要求x[i]，目前能表达的最大的数为r-1</span>
    <span class="hljs-keyword">int</span> j, k, z[maxl];
    <span class="hljs-keyword">for</span> ( j = <span class="hljs-number">0</span>; j &lt;= (___①___); j++ )
        <span class="hljs-keyword">if</span> ( y[j] &lt; m )
            <span class="hljs-keyword">for</span> ( k = <span class="hljs-number">1</span>; k &lt;= m - y[j]; k++ )
                <span class="hljs-keyword">if</span> ( y[j] + k &lt;= y[(___②___)] )
                    y[(___③___)] = y[j] + k;
    <span class="hljs-keyword">while</span> ( y[r] &lt; maxint ) r++;<span class="hljs-comment">//更新r，每一次从上一次的最大开始</span>
    <span class="hljs-keyword">if</span> ( i &gt; n )&#123;
        <span class="hljs-keyword">if</span> ( r - <span class="hljs-number">1</span> &gt; maxvalue )&#123;
            maxvalue = (___④___);
            <span class="hljs-keyword">for</span> ( j = <span class="hljs-number">1</span>; j &lt;= n; j++ )
                bestx[j] = x[j];<span class="hljs-comment">//说明此时得到了最优方案</span>
        &#125;
        <span class="hljs-keyword">return</span>;
    &#125;
    <span class="hljs-keyword">for</span> ( k = <span class="hljs-number">0</span>; k &lt; maxl; k++ )
        z[k] = y[k];<span class="hljs-comment">//由于x[i]的不同影响y[i]，所以对于每一种方案都需要一个z[i]储存</span>
    <span class="hljs-keyword">for</span> ( j = (___⑤___); j &lt;= r; j++ )&#123;
        x[i] = j;
        (___⑥___);<span class="hljs-comment">//一句话里做不到对一个数组的修改，所以显然调用了函数，只能调用backtrace()</span>
        <span class="hljs-keyword">for</span> ( k = <span class="hljs-number">0</span>; k &lt; maxl; k++ ) y[k] = z[k];
    &#125;
&#125;

<span class="hljs-keyword">void</span> main()&#123;
    <span class="hljs-keyword">int</span> j;
    <span class="hljs-built_in">printf</span>( <span class="hljs-string">&quot;input n,m:\n&quot;</span> );
    <span class="hljs-built_in">scanf</span>( “ % d % d ”, &amp;n, &amp;m );
    <span class="hljs-keyword">for</span> ( j = <span class="hljs-number">1</span>; j &lt; maxl; j++ )
        y[j] = maxint;
    y[<span class="hljs-number">0</span>] = <span class="hljs-number">0</span>; x[<span class="hljs-number">0</span>] = <span class="hljs-number">0</span>; x[<span class="hljs-number">1</span>] = <span class="hljs-number">1</span>;
    backtrace(<span class="hljs-number">2</span> , <span class="hljs-number">1</span>);
    result();
&#125;</code></pre></div>
<p> 1.<code>_______________</code><br> 2.<code>_______________</code><br> 3.<code>_______________</code><br> 4.<code>_______________</code><br> 5.<code>_______________</code><br> 6.<code>_______________</code></p>
<div class='spoiler collapsed'>
    <div class='spoiler-title'>
        解析&答案
    </div>
    <div class='spoiler-content'>
        <p>观察程序可以得到：</p>
<p>$n$表示邮票种类，<script type="math/tex">m</script>表示每封信最大能贴多少张邮票，并且已经给出四种邮票种类中的其中一种为<script type="math/tex">1</script></p>
<p>养成从<script type="math/tex">main()</script>开始看的好习惯，这里将<script type="math/tex">y[j]</script>都设置为<script type="math/tex">maxint</script>，说明默认<script type="math/tex">maxint</script>为∞，即<strong>不存在</strong>方案。</p>
<p><strong>递归/递推</strong>题都很烦，因为你不能很容易的顺着思路看出来它在干嘛。观察可得，2.3.填的东西基本上是一样的，这里要填的也就是这个算法的转移方程。这里显然是在更新<strong>最小方案数</strong>，所以我们目测方括号里要填的是<script type="math/tex">j+?</script>。</p>
<p>好了，现在<script type="math/tex">while()</script>出现了<script type="math/tex">maxint</script>，我们已经分析出来<script type="math/tex">maxint</script>表示没有方案，那么小于<script type="math/tex">maxint</script>就是说有方案。结合下标是<script type="math/tex">r</script>，后面<script type="math/tex">r</script>++，看得出这里是在检索符合条件的连续方案数量。因为<script type="math/tex">r</script><strong>需要指向下一个方案</strong>，所以表示方案数的是<script type="math/tex">r-1</script>(这里我呆瓜了好久)</p>
<p><script type="math/tex">while()</script>的之后的这个<script type="math/tex">if()</script>我们在第一次模拟的时候是会跳过的，不过没有关系。虽然我们不知道<script type="math/tex">i</script>代表了什么，但是我们知道，这里出现了对<strong>最终答案</strong>的更新，说明这里表示的是<strong>已经枚举完的</strong><script type="math/tex">m</script>张邮票的情况，由于逻辑符号<strong>不取等</strong>，所以猜测i表示的是<strong>已经枚举的</strong>邮票数<strong>+1​</strong>。结合以上分析和<strong>对称填空法</strong>，我们可以得到4.<code>r-1</code>。<del>(没想到吧！第一个出来的居然是第一次模拟跳过的！)</del></p>
<p>继续往下，观察发现<script type="math/tex">z[i]</script>只有<strong>载入</strong>和<strong>载出</strong>的操作，所以基本可以看出来它是个储存数组。想到这里你顿悟了，由于<script type="math/tex">x[i]</script>的不同会影响<script type="math/tex">y[i]</script>，所以我们需要一个<script type="math/tex">z[i]</script>来储存当前方案。<del>(然并卵)</del></p>
<p>我们看到关键语句：</p>
<div class="hljs"><pre><code class="hljs cpp">x[i] = j;</code></pre></div>

<p>什么意思？<script type="math/tex">x[i]</script>是用来放邮票的，那这句话显然是在枚举邮票啊！由于它直接对下标为<script type="math/tex">i</script>的<script type="math/tex">x</script>赋值，所以我们得到这件事情：1.我们已经枚举得到了<script type="math/tex">i-1</script>个邮票的面值；2.我们需要枚举第<script type="math/tex">i</script>个邮票的面值。我们又想起题目中要求<script type="math/tex">x[i]</script>严格递增，所以它肯定比<script type="math/tex">x[i-1]</script>大，所以我们可以得到5.<code>x[i-1]+1</code>。</p>
<p>然后我们又发现，它在枚举j的同时又不停的修复<script type="math/tex">y[i]</script>，什么意思？我们每次循环都会更改<script type="math/tex">y[i]</script>。可是我们如何在一行里更改一个数组？这时候我们又想起来作为一个<strong>递归/递推</strong>函数，只被调用了一次，而且调用的参数都是常数。<strong>灵机一动</strong>你会发现，这里要<strong>递归</strong>了。根据我们自己给的定义，现在x[i]已经有方案了，被枚举了，我们需要枚举下一个邮票，而这个过程中我们又没有增加方案，所以6.<code>backtrace(i+1,r)</code>。</p>
<p>现在还剩1.2.。刚刚在分析6.的时候我想你可能会很奇怪为什么枚举了却不增加方案，其实它把增加方案的过程放到了这里。而<script type="math/tex">j</script>枚举的是之前可以做到的最大方案数量，容易得到是1.<code>x[i-2]*(m-1)</code>。其中<script type="math/tex">x[i-2]</script>表示之前可以用的最大的邮票面值，<script type="math/tex">m-1</script>表示至少存在一个空位的情况(你如果把所有空格都占了我<script type="math/tex">x[i-1]</script>怎么办？)</p>
<p>然后，我们现在既然知道是在更新<script type="math/tex">x[i-1]</script>的方案，所以<script type="math/tex">k</script>枚举是<script type="math/tex">y[j]</script>的基础上加上<script type="math/tex">k</script>个<script type="math/tex">x[i-1]</script>的方案，得到2.3.<code>j+x[i-1]*k</code></p>
<p>1.<code>x[i-2]*(m-1)</code><br>2.<code>j+x[i-1]*k</code><br>3.<code>j+x[i-1]*k</code><br>4.<code>r-1</code><br>5.<code>x[i-1]+1</code><br>6.<code>backtrace(i+1,r)</code></p>

    </div>
</div>
<h3 id="2-x-NOIP-2008"><a href="#2-x-NOIP-2008" class="headerlink" title="[2.x]NOIP 2008"></a>[2.x]NOIP 2008</h3><p><strong>Tips:T28比T27简单很多</strong></p>
<h4 id="2-1-T27-找第k大数"><a href="#2-1-T27-找第k大数" class="headerlink" title="[2.1] T27 找第k大数"></a>[2.1] T27 找第k大数</h4><p>给定一个长度为1,000,000的无序正整数序列，以及另一个数n(1&lt;=n&lt;=1000000)，接下来以<strong>类似快速排序</strong>的方法找到序列中第n大的数(关于第n大的数：例如序列{1，2，3，4，5，6}中第3大的数是4)。</p>
<div class="hljs"><pre><code class="hljs cpp"><span class="hljs-meta">#<span class="hljs-meta-keyword">include</span> <span class="hljs-meta-string">&lt;iostream&gt;</span></span>
<span class="hljs-keyword">using</span> <span class="hljs-keyword">namespace</span> <span class="hljs-built_in">std</span>;
<span class="hljs-keyword">int</span> a[<span class="hljs-number">1000001</span>],n,ans = <span class="hljs-number">-1</span>;
<span class="hljs-function"><span class="hljs-keyword">void</span> <span class="hljs-title">swap</span><span class="hljs-params">(<span class="hljs-keyword">int</span> &amp;a,<span class="hljs-keyword">int</span> &amp;b)</span></span>&#123;
    <span class="hljs-keyword">int</span> c;
    c = a; a = b; b = c;
&#125;
<span class="hljs-function"><span class="hljs-keyword">int</span> <span class="hljs-title">FindKth</span><span class="hljs-params">(<span class="hljs-keyword">int</span> left, <span class="hljs-keyword">int</span> right, <span class="hljs-keyword">int</span> n)</span></span>&#123;
    <span class="hljs-keyword">int</span> tmp,value,i,j;
    <span class="hljs-keyword">if</span> (left == right) <span class="hljs-keyword">return</span> left;
    tmp = rand()%(right - left) + left;<span class="hljs-comment">//随机tmp</span>
    swap(a[tmp],a[left]);
    value = (___①___);
    i = left;
    j = right;
    <span class="hljs-keyword">while</span> (i &lt; j)&#123;
        <span class="hljs-keyword">while</span> (i &lt; j &amp;&amp; (___②___)) j --;
        <span class="hljs-keyword">if</span> (i &lt; j) &#123;a[i] = a[j]; i ++;&#125; <span class="hljs-keyword">else</span> <span class="hljs-keyword">break</span>;<span class="hljs-comment">//判断while是否因为②而break</span>
        <span class="hljs-keyword">while</span> (i &lt; j &amp;&amp; (___③___)) i ++;
        <span class="hljs-keyword">if</span> (i &lt; j) &#123;a[j] = a[i]; j --;&#125; <span class="hljs-keyword">else</span> <span class="hljs-keyword">break</span>;<span class="hljs-comment">//判断while是否因为③而break</span>
    &#125;
    (___④___);
    <span class="hljs-keyword">if</span> (i &lt; n) <span class="hljs-keyword">return</span>  FindKth(___⑤___);
    <span class="hljs-keyword">if</span> (i &gt; n) <span class="hljs-keyword">return</span>  (___⑥___);
    <span class="hljs-keyword">return</span> i;
&#125;
<span class="hljs-function"><span class="hljs-keyword">int</span> <span class="hljs-title">main</span><span class="hljs-params">()</span></span>&#123;
    <span class="hljs-keyword">int</span> i;
    <span class="hljs-keyword">int</span> m = <span class="hljs-number">1000000</span>;
    <span class="hljs-keyword">for</span> (i = <span class="hljs-number">1</span>;i &lt;= m;i ++)
        <span class="hljs-built_in">cin</span> &gt;&gt; a[i];
    <span class="hljs-built_in">cin</span> &gt;&gt; n;
    ans = FindKth(<span class="hljs-number">1</span>,m,n);<span class="hljs-comment">//看出函数返回的是答案下标</span>
    <span class="hljs-built_in">cout</span> &lt;&lt; a[ans];
     <span class="hljs-keyword">return</span> <span class="hljs-number">0</span>;
&#125;
</code></pre></div>
<p> 1.<code>_______________</code><br> 2.<code>_______________</code><br> 3.<code>_______________</code><br> 4.<code>_______________</code><br> 5.<code>_______________</code><br> 6.<code>_______________</code></p>
<div class='spoiler collapsed'>
    <div class='spoiler-title'>
        解析&答案
    </div>
    <div class='spoiler-content'>
        <p><del>第$k$大难道指的不是从小往大数第$k$个吗orz，我吐了，题目理解错呆瓜了半年</del></p>
<p><strong>Tips:由于题目是找第$k$大，可是程序中却用$n$表示$k$，所以我规定我用$k$表示$n$</strong></p>
<p>首先我们需要注意到题目中强调了，利用了快排的思想，看到这个题目就会好做<strong>特别多</strong>。当然前提是您还记得快排是什么。您可以看<a href="[https://weepingdemon.github.io/2019/10/17/algorithm-%E6%8E%92%E5%BA%8F%E4%B8%93%E9%A2%98/#more](https://weepingdemon.github.io/2019/10/17/algorithm-排序专题/#more">这里</a>)来回顾快排。</p>
<p>既然是快排思想，那我们肯定会想到得先选个基准数，一看就知道这里用的是$value$，而这个幸运观众就是$a[tmp]$，不过之后进行了<code>swap(a[left],a[tmp]);</code>的操作，所以之后实际上作为基准数的是$a[left]$。所以我们很好填1.<code>a[left]</code></p>
<p>熟悉快排的话一看就知道2.3.<strong>哨兵</strong>在移动，观察得到是$j$哨兵先动，而括号内填写的是哨兵所在的数和基准数的比较逻辑，由于我们需要降序数列，所以要$j$哨兵搜索<strong>大于</strong>(因为要求右侧的数具有都小于基准数的性质)基准数的。所以循环继续的条件显然是2.<code>a[j]&lt;value</code>，同理3.<code>a[i]&gt;value</code>。</p>
<p>虽然说这一部分和$quick_sort$是同原理的，但是操作过程有一个不同。哨兵找到目标下标后<strong>直接</strong>把下标<strong>赋值</strong>给了对方，这样一看你一定会想，这不是被覆盖了吗？不会错吗？其实并没有。原因有两点。</p>
<ul>
<li>其一，整个函数保证一个性质，当$a[j]&lt;value$返回$false$时，始终有$a[i]&lt;a[j]$返回$true$，因为$while()$开始后的<strong>第一个</strong>$a[i]=value$，而之后的$a[i]$都在<strong>上一次循环</strong>中保证了小于$value$。</li>
<li>其二，$while()$开始后的<strong>第一个</strong>$a[i]$被保存在value中，而每一次进行的循环时我们都进行了一次把$a[i]$变为$a[j]$的操作，一次把$a[j]$赋值为$a[i]$的操作，但是每一次的$j$都是一样的，什么意思，就是说从第一个a[i]开始，我们每次用一个数把它覆盖，但它原来的值都已经被放到别的地方了($value$或者$a[j]$或者$a[i]$)，这样我们最后会得到一个已经被存在$a[j]$的$a[i]$。也就是说$a[i]$此时是一个失效的大小，它的有效性已经被转移到$a[j]$了。</li>
</ul>
<p>$while()$的循环条件是$i&lt;j$，换言之就是$i$，$j$没相遇，现在哨兵相遇了，按照$quick_sort$的的原理，我们要把哨兵和基准数交换。基准数存在$value$中，而$a[i]$是一个失效的值。所以我们直接把$value$赋值给$a[i]$就<strong>ojbk</strong>了。4.<code>a[i]=value</code></p>
<p>5.6.明显是快排二分的过程，不过我们只需要第$k$大，所以$1$~$(k-1)$和$(k+1)$~$m$的<strong>具体大小关系不重要</strong>，我们只要知道那一部分比它大，那一部分比它小就可以了。当$i&lt;n$时，说明第$k$大在$(i+1)$~$m$，反之在$1$~$(m-1)$，所以往它在的区间二分就够了。5.<code>i+1,right,n</code>6.<code>FindKth(left,i-1,n)</code></p>
<p>1.<code>a[left]</code><br>2.<code>a[j]&lt;value</code><br>3.<code>a[i]&gt;value</code><br>4.<code>a[i]=value</code><br>5.<code>i+1,right,n</code><br>6.<code>FindKth(left,i-1,n)</code></p>

    </div>
</div>
<h4 id="2-2-T28-矩阵中的数字"><a href="#2-2-T28-矩阵中的数字" class="headerlink" title="[2.2] T28  矩阵中的数字"></a>[2.2] T28  矩阵中的数字</h4><p>有一个$n*n(1&lt;=n&lt;=5000)$的矩阵$a$， 对于$1&lt;=i &lt; n$，$1&lt;=j&lt;=n$，$ a[i,j] &lt; a[i + 1,j]$，$a[j,i] &lt; a[j,i+1]$。即矩阵中左右相邻的两个元素，右边的元素一定比左边的大。上下相邻的两个元素，下面的元素一定比上面的大。给定矩阵$a$中的一个数字$k$，找出$k$所在的行列(注意：输入数据保证矩阵中的数各不相同)。</p>
<div class="hljs"><pre><code class="hljs cpp"><span class="hljs-meta">#<span class="hljs-meta-keyword">include</span> <span class="hljs-meta-string">&lt;iostream&gt;</span></span>
<span class="hljs-keyword">using</span> <span class="hljs-keyword">namespace</span> <span class="hljs-built_in">std</span>;
<span class="hljs-keyword">int</span> n,k,answerx,answery;
<span class="hljs-keyword">int</span> a[<span class="hljs-number">5001</span>][<span class="hljs-number">5001</span>];
<span class="hljs-function"><span class="hljs-keyword">void</span> <span class="hljs-title">FindKPosition</span><span class="hljs-params">()</span></span>&#123;
    <span class="hljs-keyword">int</span> i = n,j = n;
    <span class="hljs-keyword">while</span> (j &gt; <span class="hljs-number">0</span>)&#123;
        <span class="hljs-keyword">if</span> (a[n][j] &lt; k) <span class="hljs-keyword">break</span>;               
        j --;
    &#125;
    (___①___)
    <span class="hljs-keyword">while</span> (a[i][j] != k)&#123;
        <span class="hljs-keyword">while</span> ((___②___) &amp;&amp; i &gt; <span class="hljs-number">1</span>) i --;
        <span class="hljs-keyword">while</span> ((___③___) &amp;&amp; j &lt;= n) j ++;
    &#125;
    (___④___)；
    (___⑤___)；
&#125;
<span class="hljs-function"><span class="hljs-keyword">int</span> <span class="hljs-title">main</span><span class="hljs-params">()</span></span>&#123;
    <span class="hljs-keyword">int</span> i,j;
    <span class="hljs-built_in">cin</span> &gt;&gt; n;
    <span class="hljs-keyword">for</span> (i = <span class="hljs-number">1</span>;i &lt;= n;i ++)
        <span class="hljs-keyword">for</span> (j = <span class="hljs-number">1</span>;j &lt;= n;j ++)
            <span class="hljs-built_in">cin</span> &gt;&gt; a[i][j];<span class="hljs-comment">//i行j列</span>
    <span class="hljs-built_in">cin</span> &gt;&gt; k;
    FindKPosition();
    <span class="hljs-built_in">cout</span> &lt;&lt; answerx &lt;&lt; <span class="hljs-string">&quot; &quot;</span> &lt;&lt; answery &lt;&lt; <span class="hljs-built_in">endl</span>;
     <span class="hljs-keyword">return</span> <span class="hljs-number">0</span>;
&#125;</code></pre></div>
<p> 1.<code>_______________</code><br> 2.<code>_______________</code><br> 3.<code>_______________</code><br> 4.<code>_______________</code><br> 5.<code>_______________</code></p>
<div class='spoiler collapsed'>
    <div class='spoiler-title'>
        解析&答案
    </div>
    <div class='spoiler-content'>
        <p><del>讲道理，T27和T28真的没放错位子吗……</del></p>
<p>这题没什么难度，就是从最大的数开始扫描，先往左再往上。</p>
<p>往左扫$a[n][j]&lt;k$，说明k肯定在$a[?][(j+1)$~$n]$里，所以扫完要$j++$(其实不加也不会怎样，也就后面再多扫一次)</p>
<p>往上扫的时候要注意，它不一定是在正上方，所以先往上找比它小的，如果它就在这一列那它肯定会先被扫到，如果不在这一行，那么一定在这个比它小的数的右边。</p>
<p>1.<code>j++</code><br>2.<code>a[i][j]&gt;k</code><br>3.<code>a[i][j]&lt;k</code><br>4.<code>answerx=i</code><br>5.<code>answery=j</code></p>

    </div>
</div>
<h3 id="3-x-NOIP-2009"><a href="#3-x-NOIP-2009" class="headerlink" title="[3.x]NOIP 2009"></a>[3.x]NOIP 2009</h3><h4 id="3-1-T27-最大连续子段和"><a href="#3-1-T27-最大连续子段和" class="headerlink" title="[3.1] T27 最大连续子段和"></a>[3.1] T27 最大连续子段和</h4><p>给出一个数列（元素个数不多于100），数列元素均为负整数、正整数、0。请找出数列中的一个<strong>连续</strong>子数列，使得这个子数列中包含的<strong>所有元素之和最大</strong>，在和最大的前提下还要求该子数列包含的元素<strong>个数最多</strong>，并输出这个<strong>最大和</strong>以及该连续子数列中<strong>元素的个数</strong>。例如：</p>
<div class="table-container">
<table>
<thead>
<tr>
<th>输入：</th>
<th>输出：</th>
</tr>
</thead>
<tbody>
<tr>
<td>4 -5 3 2 4</td>
<td>9 3</td>
</tr>
<tr>
<td>1 2 3 -5 0 7 8</td>
<td>16 7</td>
</tr>
</tbody>
</table>
</div>
<div class="hljs"><pre><code class="hljs cpp"><span class="hljs-meta">#<span class="hljs-meta-keyword">include</span> <span class="hljs-meta-string">&lt;iostream&gt;</span></span>
<span class="hljs-keyword">using</span> <span class="hljs-keyword">namespace</span> <span class="hljs-built_in">std</span>;
<span class="hljs-keyword">int</span> a[<span class="hljs-number">101</span>];
<span class="hljs-keyword">int</span> n,i,ans,len,tmp,beg,end;
<span class="hljs-function"><span class="hljs-keyword">int</span> <span class="hljs-title">main</span><span class="hljs-params">()</span></span>&#123;
    <span class="hljs-built_in">cin</span> &gt;&gt; n;
    <span class="hljs-keyword">for</span> (i=<span class="hljs-number">1</span>;i&lt;=n;i++)
        <span class="hljs-built_in">cin</span> &gt;&gt; a[i];
    tmp=<span class="hljs-number">0</span>; ans=<span class="hljs-number">0</span>; len=<span class="hljs-number">0</span>; beg=(___①___);
    <span class="hljs-keyword">for</span> (i=<span class="hljs-number">1</span>;i&lt;=n;i++)&#123;
        <span class="hljs-keyword">if</span> (tmp+a[i]&gt;ans)&#123;
            ans=tmp+a[i];
            len=i-beg;
        &#125;
        <span class="hljs-keyword">else</span> <span class="hljs-keyword">if</span> ((___②___) &amp;&amp;i-beg&gt;len)
            len=i-beg;<span class="hljs-comment">//上一个if到这里为止是在和答案比较</span>
        <span class="hljs-keyword">if</span> (tmp+a[i](___③___))&#123;
            beg=(___④___);
            tmp=<span class="hljs-number">0</span>;
        &#125;
        <span class="hljs-keyword">else</span> (___⑤___);<span class="hljs-comment">//上一个if到这里为止是在更新前缀和</span>
    &#125;
    <span class="hljs-built_in">cout</span> &lt;&lt; ans &lt;&lt; <span class="hljs-string">&quot; &quot;</span> &lt;&lt; len &lt;&lt; <span class="hljs-built_in">endl</span>;
    <span class="hljs-keyword">return</span> <span class="hljs-number">0</span>;
&#125;</code></pre></div>
<p> 1.<code>_______________</code><br> 2.<code>_______________</code><br> 3.<code>_______________</code><br> 4.<code>_______________</code><br> 5.<code>_______________</code></p>
<div class='spoiler collapsed'>
    <div class='spoiler-title'>
        解析&答案
    </div>
    <div class='spoiler-content'>
        <p>前缀和嘛。</p>
<p><del>你挖空非要挖这么奇怪的吗……</del></p>
<p>$beg$其实是用来标记目前数列是从哪里开始的(目前数列前面一位)，所以只是用来计算len的。($len=i-beg$)。将$if$和$else$ $if$匹配后分组来看代码会好做很多。</p>
<p>1.<code>0</code><br>2.<code>tmp+a[i]=ans</code><br>3.<code>&lt;0</code><br>4.<code>i</code><br>5.<code>tmp+=a[i]</code></p>

    </div>
</div>
<h4 id="3-2-T28-寻找等差数列"><a href="#3-2-T28-寻找等差数列" class="headerlink" title="[3.2] T28 寻找等差数列"></a>[3.2] T28 寻找等差数列</h4><p>有一些长度相等的<strong>等差数列</strong>(数列中每个数都为0~59的整数)，设长度<strong>均为$L$</strong>，将等差数列中的所有数打乱顺序放在一起。现在给你这些打乱后的数，问原先，<strong>L最大可能为多大</strong>？先读入一个数$n$（$1&lt;=n&lt;=60$），再读入$n$个数，代表打乱后的数。输出等差数列最大可能长度$L$。</p>
<div class="hljs"><pre><code class="hljs cpp"><span class="hljs-meta">#<span class="hljs-meta-keyword">include</span> <span class="hljs-meta-string">&lt;iostream&gt;</span></span>
<span class="hljs-keyword">using</span> <span class="hljs-keyword">namespace</span> <span class="hljs-built_in">std</span>;
<span class="hljs-keyword">int</span> hash[<span class="hljs-number">60</span>];
<span class="hljs-keyword">int</span> n, x, ans, maxnum;
<span class="hljs-function"><span class="hljs-keyword">int</span> <span class="hljs-title">work</span><span class="hljs-params">(<span class="hljs-keyword">int</span> now)</span> </span>&#123;
    <span class="hljs-keyword">int</span> first, second, delta, i;
    <span class="hljs-keyword">int</span> ok;
    <span class="hljs-keyword">while</span> ((___①___) &amp;&amp; !hash[now])
        ++now;
    <span class="hljs-keyword">if</span> (now &gt; maxnum)
        <span class="hljs-keyword">return</span> <span class="hljs-number">1</span>;
    first = now;
    <span class="hljs-keyword">for</span> (second = first; second &lt;= maxnum; second++)
        <span class="hljs-keyword">if</span> (hash[second]) &#123;
            delta = (___②___);
            <span class="hljs-keyword">if</span> (first + delta * (___③___)&gt; maxnum) 
                <span class="hljs-keyword">break</span>;
            <span class="hljs-keyword">if</span> (delta == <span class="hljs-number">0</span>)
                ok = (___④___);
            <span class="hljs-keyword">else</span>&#123;
                ok = <span class="hljs-number">1</span>;
                <span class="hljs-keyword">for</span> (i = <span class="hljs-number">0</span>; i &lt; ans; i++)
                    ok = (___⑤___) &amp;&amp; (hash[first+delta*i]); 
            &#125;
            <span class="hljs-keyword">if</span> (ok)&#123;
                <span class="hljs-keyword">for</span> (i = <span class="hljs-number">0</span>; i &lt; ans; i++)
                    hash[first+delta*i]--;
                <span class="hljs-keyword">if</span> (work(first)) <span class="hljs-keyword">return</span> <span class="hljs-number">1</span>;
                <span class="hljs-keyword">for</span> (i = <span class="hljs-number">0</span>; i &lt; ans; i++)
                    hash[first+delta*i]++;
            &#125;
        &#125;
    <span class="hljs-keyword">return</span> <span class="hljs-number">0</span>;
&#125;
<span class="hljs-function"><span class="hljs-keyword">int</span> <span class="hljs-title">main</span><span class="hljs-params">()</span></span>&#123;
    <span class="hljs-keyword">int</span> i;
    <span class="hljs-built_in">memset</span>(hash, <span class="hljs-number">0</span>, <span class="hljs-keyword">sizeof</span>(hash));
    <span class="hljs-built_in">cin</span> &gt;&gt; n;
    maxnum = <span class="hljs-number">0</span>;
    <span class="hljs-keyword">for</span> (i = <span class="hljs-number">0</span>; i &lt; n; i++)&#123;
        <span class="hljs-built_in">cin</span> &gt;&gt; x;
        hash[x]++;
        <span class="hljs-keyword">if</span> (x &gt; maxnum)
            maxnum = x;<span class="hljs-comment">//标记最大</span>
    &#125;
    <span class="hljs-keyword">for</span> (ans = n; ans &gt;= <span class="hljs-number">1</span>; ans--)
        <span class="hljs-keyword">if</span> ( n%ans==<span class="hljs-number">0</span> &amp;&amp; (___⑥___))&#123;
            <span class="hljs-built_in">cout</span> &lt;&lt; ans &lt;&lt; <span class="hljs-built_in">endl</span>;
            <span class="hljs-keyword">break</span>;
        &#125;
    <span class="hljs-keyword">return</span> <span class="hljs-number">0</span>;
&#125;</code></pre></div>
<p> 1.<code>_______________</code><br> 2.<code>_______________</code><br> 3.<code>_______________</code><br> 4.<code>_______________</code><br> 5.<code>_______________</code><br> 6.<code>_______________</code></p>
<div class='spoiler collapsed'>
    <div class='spoiler-title'>
        解析&答案
    </div>
    <div class='spoiler-content'>
        <p>(从$main()$开始看)看到$hash[x]$我们就想到$hash[i]$在这里是个桶，目的是为了检查相对应的数字是否还有。可以看到程序中还顺便找了一手最大值。然后我们会发现，整个$main()$里没有出现$work()$函数，所以我们就知道6.是填$work(?)$。同时我们注意到，输出答案的一个条件是$n\%ans==0$返回<strong>真</strong>，这显然，因此我们也只需要考虑<strong>满足性质的$ans$</strong>。</p>
<p>$work()$的第一个$while()$继续执行的一个条件是$hash[now]$为空，执行的内容是$now$右移，灵机一动，相信你多多少少猜到了这是在找目前还可以用的数中的最小值，也就是等差数列的首项。下面的$if$中，如果$now&gt;maxnum$返回<strong>真</strong>就表示已经没有可以用的数了，所以返回真，也就是搜索完成。但是，如果只依靠已有的条件，如果此时$hash[i]$全为空，会陷入死循环，所以我们要给$now$加一个限制条件1.<code>now&lt;=maxnum</code>。而其后的$first=now$也可以印证我们刚刚的猜想，$first$ $first$，就是第一个的意思嘛。那挠挠肚皮我们就可以类比出来，$second$表示$a_2$，$delta$表示公差，这里没有枚举公差的部分，却有枚举$a_2$的部分，所以只能用$\Delta=a_2-a_1$来计算公差了。2.<code>second-first</code></p>
<p>观察3.所在的一行，是在判某个数是否小于等于最大数，也就是是否有可能存在这个数，再观察表达式，是不是和$a_n=a_1+(n-1)*\Delta$的计算公式很像？那就对了嘛！那$n$是多少？$ans$！我是说，$n=ans$。3.<code>ans-1</code></p>
<p>4.所在的if的判断条件是$delta=0$返回真，那就是一个常数列嘛。那你得看看是不是有$ans$个$a_1$大小的数，所以自然是$hash[first]&gt;=ans$。(我毛估估觉得$hash[first]==0$得挂，万一我把一个常数列分成两个等长的同样的数列是不是也是一种方案呢？不太清楚xd)</p>
<p>其后$else$一下就是说它不是个常数列，所以要判断每一项是否存在库存，这就要求$hash[a_n]$都返回真，也就是$hash[a_1]$ &amp;&amp; $hash[a_2]$ &amp;&amp; $hash[a_3]$ &amp;&amp; … &amp;&amp; $hash[a_n] = 1$，写成循环的形式就是<code>ok = ok &amp;&amp; (hash[first+delta*i]);</code>也就是说5.<code>ok</code>。</p>
<p>在上面的分析中我们知道$now$指的是当前的位置，那大概是从0开始扫($work(1)$似乎也没什么问题？</p>
<p>1.<code>now&lt;=maxnum</code><br>2.<code>second-first</code><br>3.<code>ans-1</code><br>4.<code>hash[first]&gt;=ans</code><br>5.<code>ok</code><br>6.<code>work(0)</code></p>

    </div>
</div>
<link rel="stylesheet" href="/blog/css/spoiler.css" type="text/css"><script src="/blog/js/spoiler.js" type="text/javascript" async></script>
            </div>
            <hr>
            <div>
              <div class="post-metas mb-3">
                
                  <div class="post-meta mr-3">
                    <i class="iconfont icon-category"></i>
                    
                      <a class="hover-with-bg" href="/blog/categories/%E7%AE%97%E6%B3%95/">算法</a>
                    
                  </div>
                
                
                  <div class="post-meta">
                    <i class="iconfont icon-tags"></i>
                    
                      <a class="hover-with-bg" href="/blog/tags/%E7%AE%97%E6%B3%95/">算法</a>
                    
                      <a class="hover-with-bg" href="/blog/tags/%E4%BF%A1%E5%A5%A5/">信奥</a>
                    
                      <a class="hover-with-bg" href="/blog/tags/%E4%B8%93%E9%A2%98/">专题</a>
                    
                  </div>
                
              </div>
              
                <p class="note note-warning">未经允许禁止用于商业用途，转载请标注出处和作者！</p>
              
              
                <div class="post-prevnext row">
                  <article class="post-prev col-6">
                    
                    
                      <a href="/blog/2019/10/17/algSORT/">
                        <i class="iconfont icon-arrowleft"></i>
                        <span class="hidden-mobile">algorithm-排序专题</span>
                        <span class="visible-mobile">上一篇</span>
                      </a>
                    
                  </article>
                  <article class="post-next col-6">
                    
                    
                      <a href="/blog/2019/10/07/artYiJian/">
                        <span class="hidden-mobile">article-一箭</span>
                        <span class="visible-mobile">下一篇</span>
                        <i class="iconfont icon-arrowright"></i>
                      </a>
                    
                  </article>
                </div>
              
            </div>

            
              <!-- Comments -->
              <article class="comments" id="comments">
                
                <!-- 来必力City版安装代码 -->
<div id="lv-container" data-id="city" data-uid="MTAyMC80ODI4NS8yNDc3OQ==">
  <script type="text/javascript">
     (function(d, s) {
         var j, e = d.getElementsByTagName(s)[0];
  
         if (typeof LivereTower === 'function') { return; }
  
         j = d.createElement(s);
         j.src = 'https://cdn-city.livere.com/js/embed.dist.js';
         j.async = true;
  
         e.parentNode.insertBefore(j, e);
     })(document, 'script');
  </script>
  <noscript>为正常使用来必力评论功能请激活JavaScript</noscript>
  </div>
  <!-- City版安装代码已完成 -->
              </article>
            
          </article>
        </div>
      </div>
    </div>
    
      <div class="d-none d-lg-block col-lg-2 toc-container" id="toc-ctn">
        <div id="toc">
  <p class="toc-header"><i class="iconfont icon-list"></i>&nbsp;目录</p>
  <div id="tocbot"></div>
</div>

      </div>
    
  </div>
</div>

<!-- Custom -->

  <div class="col-lg-7 mx-auto nopadding-md">
    <div class="container custom post-content mx-auto">
      <p><center><b>(っ*´Д`)っ㊖ <font color="darkblue">  疯 狂 暗 示  </font>(っ*´Д`)っ㊖</b></center></p><center><img src="https://pic.downk.cc/item/5f3bd3b414195aa59408fb13.png" srcset="/blog/img/loading.gif" width="50%" height="50%"/></center>
    </div>
  </div>


    
  </main>

  
    <a id="scroll-top-button" href="#" role="button">
      <i class="iconfont icon-arrowup" aria-hidden="true"></i>
    </a>
  

  
    <div class="modal fade" id="modalSearch" tabindex="-1" role="dialog" aria-labelledby="ModalLabel"
     aria-hidden="true">
  <div class="modal-dialog modal-dialog-scrollable modal-lg" role="document">
    <div class="modal-content">
      <div class="modal-header text-center">
        <h4 class="modal-title w-100 font-weight-bold">搜索</h4>
        <button type="button" id="local-search-close" class="close" data-dismiss="modal" aria-label="Close">
          <span aria-hidden="true">&times;</span>
        </button>
      </div>
      <div class="modal-body mx-3">
        <div class="md-form mb-5">
          <input type="text" id="local-search-input" class="form-control validate">
          <label data-error="x" data-success="v"
                 for="local-search-input">关键词</label>
        </div>
        <div class="list-group" id="local-search-result"></div>
      </div>
    </div>
  </div>
</div>
  

  
    <!-- APlayer 音乐播放器 -->
    <div id="aplayer"></div>
    <script defer src="https://cdn.staticfile.org/aplayer/1.10.1/APlayer.min.js" ></script>
<link  rel="stylesheet" href="https://cdn.staticfile.org/aplayer/1.10.1/APlayer.min.css" />
<script type="text/javascript">
  var oldLoadAp = window.onload;
  window.onload = function () {
    oldLoadAp && oldLoadAp();

    new APlayer({
      container: document.getElementById('aplayer'),
      fixed: true,
      autoplay: 'false' === 'true',
      loop: 'all',
      order: 'random',
      theme: '#708090',
      preload: 'none',
      audio: [{"name":"SLEEPWALK","artist":"冰镇豆沙君","url":"http://music.163.com/song/media/outer/url?id=1417007045.mp3","cover":"/img/cover.jpg"},{"name":"雨き声残响","artist":"冰镇豆沙君","url":"http://music.163.com/song/media/outer/url?id=1318309030.mp3","cover":"/img/cover.jpg"},{"name":"春を告げる","artist":"茶玖","url":"http://music.163.com/song/media/outer/url?id=1460240705.mp3","cover":"/img/cover.jpg"},{"name":"ベクターフィッシュ","artist":"茶玖","url":"http://music.163.com/song/media/outer/url?id=1445572300.mp3","cover":"/img/cover.jpg"},{"name":"红莲华","artist":"噢耶","url":"http://music.163.com/song/media/outer/url?id=1397590357.mp3","cover":"/img/cover.jpg"},{"name":"横竖撇点折","artist":"噢耶","url":"http://music.163.com/song/media/outer/url?id=1421414775.mp3","cover":"/img/cover.jpg"},{"name":"たぶん","artist":"真央","url":"http://music.163.com/song/media/outer/url?id=1464762744.mp3","cover":"/img/cover.jpg"},{"name":"夜に駆ける","artist":"真央","url":"http://music.163.com/song/media/outer/url?id=1461930738.mp3","cover":"/img/cover.jpg"},{"name":"Alice","artist":"yakuri","url":"http://music.163.com/song/media/outer/url?id=1431092750.mp3","cover":"/img/cover.jpg"},{"name":"起风了","artist":"yakuri","url":"http://music.163.com/song/media/outer/url?id=1367440424.mp3","cover":"/img/cover.jpg"}]
    });
  }
</script>

  

  

  <footer class="mt-5">
  <div class="text-center py-3">
    <div>
      <a href="https://hexo.io" target="_blank" rel="nofollow noopener"><span>Hexo</span></a>
      <i class="iconfont icon-love"></i>
      <a href="https://github.com/fluid-dev/hexo-theme-fluid" target="_blank" rel="nofollow noopener">
        <span>Fluid</span></a>
    </div>
    
  <div class="statistics">
    
    

    
      
        <!-- 不蒜子统计PV -->
        <span id="busuanzi_container_site_pv" style="display: none">
            总访问量 
            <span id="busuanzi_value_site_pv"></span>
             次
          </span>
      
      
        <!-- 不蒜子统计UV -->
        <span id="busuanzi_container_site_uv" style="display: none">
            总访客数 
            <span id="busuanzi_value_site_uv"></span>
             人
          </span>
      
    
  </div>


    

    
  </div>
</footer>

<!-- SCRIPTS -->
<script  src="https://cdn.staticfile.org/jquery/3.4.1/jquery.min.js" ></script>
<script  src="https://cdn.staticfile.org/twitter-bootstrap/4.4.1/js/bootstrap.min.js" ></script>
<script  src="/blog/js/debouncer.js" ></script>
<script  src="/blog/js/main.js" ></script>

<!-- Plugins -->


  
    <script  src="/blog/js/lazyload.js" ></script>
  



  <script defer src="https://cdn.staticfile.org/clipboard.js/2.0.6/clipboard.min.js" ></script>
  <script  src="/blog/js/clipboard-use.js" ></script>



  <script defer src="https://busuanzi.ibruce.info/busuanzi/2.3/busuanzi.pure.mini.js" ></script>





  <script  src="https://cdn.staticfile.org/tocbot/4.11.1/tocbot.min.js" ></script>
  <script>
    $(document).ready(function () {
      var boardCtn = $('#board-ctn');
      var boardTop = boardCtn.offset().top;

      tocbot.init({
        tocSelector: '#tocbot',
        contentSelector: '#post-body',
        headingSelector: 'h1,h2,h3,h4,h5,h6',
        linkClass: 'tocbot-link',
        activeLinkClass: 'tocbot-active-link',
        listClass: 'tocbot-list',
        isCollapsedClass: 'tocbot-is-collapsed',
        collapsibleClass: 'tocbot-is-collapsible',
        collapseDepth: 6,
        scrollSmooth: true,
        headingsOffset: -boardTop
      });
      if ($('.toc-list-item').length > 0) {
        $('#toc').css('visibility', 'visible');
      }
    });
  </script>



  <script  src="https://cdn.staticfile.org/typed.js/2.0.11/typed.min.js" ></script>
  <script>
    var typed = new Typed('#subtitle', {
      strings: [
        '  ',
        "algorithm-历届程序填空专题&nbsp;",
      ],
      cursorChar: "_",
      typeSpeed: 50,
      loop: false,
    });
    typed.stop();
    $(document).ready(function () {
      $(".typed-cursor").addClass("h2");
      typed.start();
    });
  </script>





  <script  src="/blog/js/local-search.js" ></script>
  <script>
    var path = "/blog/local-search.xml";
    var inputArea = document.querySelector("#local-search-input");
    inputArea.onclick = function () {
      searchFunc(path, 'local-search-input', 'local-search-result');
      this.onclick = null
    }
  </script>



  <script  src="https://cdn.staticfile.org/fancybox/3.5.7/jquery.fancybox.min.js" ></script>
  <link  rel="stylesheet" href="https://cdn.staticfile.org/fancybox/3.5.7/jquery.fancybox.min.css" />

  <script>
    $('#post img:not(.no-zoom img, img[no-zoom]), img[zoom]').each(
      function () {
        var element = document.createElement('a');
        $(element).attr('data-fancybox', 'images');
        $(element).attr('href', $(this).attr('src'));
        $(this).wrap(element);
      }
    );
  </script>





  

  
    <!-- MathJax -->
    <script>
      MathJax = {
        tex: {
          inlineMath: [['$', '$'], ['\\(', '\\)']]
        },
        options: {
          renderActions: {
            findScript: [10, doc => {
              document.querySelectorAll('script[type^="math/tex"]').forEach(node => {
                const display = !!node.type.match(/; *mode=display/);
                const math = new doc.options.MathItem(node.textContent, doc.inputJax[0], display);
                const text = document.createTextNode('');
                node.parentNode.replaceChild(text, node);
                math.start = { node: text, delim: '', n: 0 };
                math.end = { node: text, delim: '', n: 0 };
                doc.math.push(math);
              });
            }, '', false],
            insertedScript: [200, () => {
              document.querySelectorAll('mjx-container').forEach(node => {
                let target = node.parentNode;
                if (target.nodeName.toLowerCase() === 'li') {
                  target.parentNode.classList.add('has-jax');
                }
              });
            }, '', false]
          }
        }
      };
    </script>

    <script async src="https://cdn.staticfile.org/mathjax/3.0.5/es5/tex-svg.js" ></script>

  



  
  
    <script type="text/javascript">
      //定义获取词语下标
      var a_idx = 0;
      jQuery(document).ready(function ($) {
        //点击body时触发事件
        $("body").click(function (e) {
          //需要显示的词语
          var a = new Array("富强", "民主", "文明", "和谐", "自由", "平等", "公正", "法治", "爱国", "敬业", "诚信", "友善");
          //设置词语给span标签
          var $i = $("<span/>").text(a[a_idx]);
          //下标等于原来下标+1  余 词语总数
          a_idx = (a_idx + 1) % a.length;
          //获取鼠标指针的位置，分别相对于文档的左和右边缘。
          //获取x和y的指针坐标
          var x = e.pageX, y = e.pageY;
          //在鼠标的指针的位置给$i定义的span标签添加css样式
          $i.css({
            "z-index": 999,
            "top": y - 20,
            "left": x,
            "position": "absolute",
            "font-weight": "bold",
            "color": rand_color()
          });
          // 随机颜色
          function rand_color() {
            return "rgb(" + ~~(255 * Math.random()) + "," + ~~(255 * Math.random()) + "," + ~~(255 * Math.random()) + ")"
          }
          //在body添加这个标签
          $("body").append($i);
          //animate() 方法执行 CSS 属性集的自定义动画。
          //该方法通过CSS样式将元素从一个状态改变为另一个状态。CSS属性值是逐渐改变的，这样就可以创建动画效果。
          //详情请看http://www.w3school.com.cn/jquery/effect_animate.asp
          $i.animate({
            //将原来的位置向上移动180
            "top": y - 180,
            "opacity": 0
            //1500动画的速度
          }, 1500, function () {
            //时间到了自动删除
            $i.remove();
          });
        });
      })
      ;
    </script>
  














<script src="/blog/live2dw/lib/L2Dwidget.min.js?094cbace49a39548bed64abff5988b05"></script><script>L2Dwidget.init({"pluginRootPath":"live2dw/","pluginJsPath":"lib/","pluginModelPath":"assets/","tagMode":false,"debug":false,"model":{"scale":1,"hHeadPos":0.5,"vHeadPos":0.618,"jsonPath":"/blog/live2dw/assets/assets/hijiki.model.json"},"display":{"superSample":1,"width":150,"height":300,"position":"right","hOffset":0,"vOffset":-20},"mobile":{"show":true,"scale":1},"react":{"opacityDefault":0.7,"opacityOnHover":0.2},"log":false});</script></body>
</html>
